Accurate information about a topology of a computer network is essential for system management tasks such as problem determination and performance analysis. However, this information is not always readily available, even within the boundaries of a company, especially if the intranet of the company is very large and consists of multiple subnetworks that are managed by different organizations. It is known that combining such information manually from multiple sources, and especially keeping it up to date, turns out to be quite tedious and time consuming. Moreover, collecting such information becomes even more complicated for the Internet, where different parts of the network are owned by different organizations.
Currently, there are two common approaches to Internet structure discovery. One approach collects information from Border Gateway Protocol (BGP) inter-domain routing tables, and the other approach actively probes Internet Protocol (IP) addresses to trace the actual paths that packets traverse from source to destination.
Some examples of techniques in the latter approach are as follows. The approach of R. Siamwalla et al., “Discovering Internet Topology,” IEEE INFOCOM '99, pp 1-16, 1999, uses several heuristics and algorithms to discover network topology. The basic idea described in their work is to start from some initial set of IP addresses, and iteratively expand this set to obtain additional IP addresses, until all addresses are discovered.
The procedure for expanding the current set of addresses is based on the assumption that network services (such as Simple Network Management Protocol (SNMP), broadcast ping, Domain Name Service (DNS) zone transfer, etc.) are enabled and users have the access privilege to use them. Using network services can help to create more accurate topology maps. Many researcher and commercial tools for network discovery rely on these services, in particular on the information provided by SNMP. These tools include OpenView from Hewlett Packard, Tivoli from IBM Corporation, Intermapper from Dartware, and Netviz products.
A similar technique can also be used for the multicast overlay network of the Internet, i.e., the M-Bone, as described in A. Reddy et al., “Large-Scale Fault Isolation,” IEEE Journal of Selected Areas in Communication Special Issue on Network Management, 2000. Routers on the M-Bone can request a list of neighbor routers through the services. However, using this approach requires running SNMP service on every node from which information is to be obtained, which can be expensive. Also, network administrators can be reluctant to provide this service because of excessive load (or even potential denial-of-service attacks). Thus, not all the nodes in a given network may be SNMP-enabled.
Other works such as are described in B. Huffaker et al., “Topology Discovery by Active Probing, Symposium on Applications and the Internet (SAINT),” 2002 and in B. Cheswick et al., “Mapping and Visualizing the Internet,” Proceedings of the 2000 USENIX Annual Technical Conference, June 2000, use traceroute style packets to map outgoing paths from a single source or multiple sources to each of the targets on the Internet.
As is known, a traceroute utility works by increasing the “time-to-live” (TTL) value of each successive batch of packets sent. The first three packets have a TTL value of one (implying that they make a single hop—a hop being a traversal of one or more packets from one node to another node). The next three packets have a TTL value of two, and so on. When a packet passes through a host node, normally the host decrements the TTL value by one, and forwards the packet to the next host. When a packet with a TTL of one reaches a host, the host discards the packet and sends an Internet Control Message Protocol (ICMP) time-exceeded packet to the sender. The traceroute utility uses these returning packets to produce a list of hosts, in terms of hops, that the packets have traversed en route to the destination.
However, using only source-destination traceroutes does not always give complete information about the topology, and may result in biased sampling, especially if the number of sources is small.
Accordingly, a need exists for improved network topology discovery techniques.